package com.leetcode.www;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
 *
 * 实现 Solution 类：
 *
 * Solution(ListNode head) 使用整数数组初始化对象。
 * int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/linked-list-random-node
 * User:yxd
 * Date:2022-01-17
 * Time:0:03
 */
/*public class ListNode {此包中已有一个ListNode了
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}*/
class Solution {
    public List<Integer> list;
    Random random;
    public Solution(ListNode head) {
        list = new ArrayList<>();
        while(head != null){//增加元素
            list.add(head.val);
            head = head.next;
        }
        random = new Random();//随机数
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));//随机获得一个元素

    }
}
public class Everyday382 {
    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);

        Solution solution = new Solution(list1);
        System.out.println(solution.getRandom());
    }
}
